#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <utility>
#include <fstream>

//делать шаг через nullPosition
using namespace std;
class vertex{
public:
    vertex(){}
    vertex(const vector<int>& position,int heurestics = -1){
        code = 0;
        for (int i = 0; i < 9; i++){
            if (position[i] == 0){
                 nullPosition = i;
             }
            code*=9;
            code+=position[i];
        }
        if (heurestics == -1){
            heuresticFunction = 0;
            for (int i = 0; i < 9; i++){
                if (position[i] != 0){
                    heuresticFunction += abs(i%3 - (position[i]-1)%3)
                        +abs(i/3 - (position[i]-1)/3);
                }
            }
        }else{
            heuresticFunction = heurestics;
        }
        parent = code;
        costFromStart = 0;
        heuresticCost = heuresticFunction + costFromStart;
    }

    vertex& operator = (const vertex& other){
        parent = other.parent;
        code = other.code;
        nullPosition = other.nullPosition;
        heuresticFunction = other.heuresticFunction;
        heuresticCost = other.heuresticCost;
        costFromStart = other.costFromStart;
        return *this;
    }
    vertex(const vertex& other){
        *this = other;
    }

    vector<int> decode()const{
        vector<int> decode (9);
        int ccode = code;
        for (int i = 0; i < 9; i++){
            decode[8-i] = ccode % 9;
            ccode /= 9;
        }
        return decode;
    }

    pair<int,vector<vertex> > getNeighbors(){
        int numberOfChildren = 0;
        vector<int> position (9);
        vector<vertex> answer (4);
        position = this->decode();
        //l
        if(nullPosition % 3 > 0){
            int first = nullPosition - 1;
            int second = nullPosition;
            swap(position[first],position[second]);
            numberOfChildren += 1;
            answer[numberOfChildren - 1] = vertex(position,-1);
            swap(position[first],position[second]);
        }
        //d
        if(nullPosition / 3 < 2){
            int first = nullPosition + 3;
            int second = nullPosition;
            swap(position[first],position[second]);
                        numberOfChildren += 1;
            answer[numberOfChildren - 1] = vertex(position,-1);
            swap(position[first],position[second]);
        }
        //r
        if(nullPosition % 3 < 2){
            int first = nullPosition + 1;
            int second = nullPosition;
            swap(position[first],position[second]);
            numberOfChildren += 1;
            answer[numberOfChildren - 1] = vertex(position,-1);
            swap(position[first],position[second]);
        }
        //u
        if(nullPosition / 3 > 0){
            int first = nullPosition - 3;
            int second = nullPosition;
            swap(position[first],position[second]);
            numberOfChildren += 1;
            answer[numberOfChildren - 1] = vertex(position,-1);
            swap(position[first],position[second]);
        }
        return pair<int,vector<vertex> >(numberOfChildren,answer);
    }

    int getHeuresticsCost()const{
        return heuresticCost;
    }

    int getCostFromStart()const{
        return costFromStart;
    }

    int getCode()const{
        return code;
    }

    int getNullPosition(){
        return nullPosition;
    }

    bool operator < (const vertex& other) const{
            return code < other.code;
    }

    bool operator ==(const vertex& other) const{
        return code == other.code;
    }

    bool operator !=(const vertex& other) const{
        return !(*this == other);
    }

    int getParent()const{
        return parent;
    }

    void setProperties( int cost, const int& newParent) {
        costFromStart = cost;
        heuresticCost = costFromStart + heuresticFunction;
        parent = newParent;
    }

    bool hasSolution() const {
        vector<int> position(9);
        position = this->decode();
        int countInversions = 0;
        for (int i = 0; i < 8; i++){
            for (int j = i + 1; j < 9; j++){
                if(position[i] > position[j] && position[j] != 0){
                     countInversions += 1;
                }
            }
        }
        countInversions += (3%2 - 1)*(nullPosition/3);
        int isSolvable = countInversions % 2 == 0;
        return isSolvable;
    }

private:
int parent;
int code;
int nullPosition;
int heuresticFunction;//эвристическая функция
int heuresticCost;//длина предполагаемого пути с учетом эвристики
int costFromStart;//длина действительного пути от старта. у только сконструированной вершины 0
};


 vector< vertex > AStar(const vertex& start, const  vertex& finish ) {
    vector< vertex > result;
    set< int > closed;
    set< int > open;
    set< pair<int,  vertex > > openWithCost;
    map <int,vertex> toFindWay;
    open.insert( start.getCode() );
    openWithCost.insert(make_pair(start.getHeuresticsCost(),start));
    toFindWay[start.getCode()] = start;
    while( !open.empty() ) {
        //берём вершину с наименьшей эвристической функцией
        vertex currVertex = openWithCost.begin()->second;

        if( currVertex == finish ) {
            while(currVertex != start){
                result.push_back(currVertex);
                currVertex = toFindWay[currVertex.getParent()];
            }
            result.push_back(currVertex);
            return result;
        }
        //обрабатываем текущую вершину
        closed.insert( currVertex.getCode() );
        open.erase(currVertex.getCode());
        openWithCost.erase( openWithCost.begin() );
        // Проверяем каждого соседа currVertex
        pair<int,vector <vertex> > neighbors = currVertex.getNeighbors();
        for( int i = 0; i < neighbors.first; i++ ) {
             vertex currNeighbor = neighbors.second[i];
            // Пропускаем закрытых соседей

            if( closed.find(currNeighbor.getCode()) == closed.end() ) {
                //Вычисляем стоимость пути для обрабатываемого соседа
                int newCost = currVertex.getCostFromStart() + 1;
                bool newCostIsBetter = false;
                //если еще не был открыт, добавим в открытые
                if( open.find(currNeighbor.getCode()) == open.end() ) {
                    open.insert( currNeighbor.getCode() );
                    newCostIsBetter = true;
                } else {
                    //currNeighbor - свежесконструированный узел, в нем costFromStart = 0;
                    //поэтому сравнение корректно
                    if( newCost + currNeighbor.getHeuresticsCost()
                            < toFindWay[currNeighbor.getCode()].getHeuresticsCost()) {
                        //новая стоимость оказалась лучше
                        newCostIsBetter = true;
                    }
                }
                //иначе новая стоимость хуже и мы оставляем всё как есть
                //Обновление данных
                if( newCostIsBetter ) {
                    currNeighbor.setProperties(newCost, currVertex.getCode());
                    openWithCost.insert(
                    make_pair( currNeighbor.getHeuresticsCost(), currNeighbor ) );
                    toFindWay[currNeighbor.getCode()] = currNeighbor;
                }
            }
        }
    }
    return result;
}
void doTask(const vertex& from ) {
    vector<int> to (9);
    for(int i = 1; i <10; i++){
        to[i-1] = i%9;
    }
    if(!from.hasSolution()) {
        cout << "No" << "\n";
        return;
    }
    vertex end(to);
    std::vector<vertex> path = AStar( from, end );
    if( path.size() == 0 ) {
        cout << "No" << std::endl;
        return;
    }
    cout << "Yes" << endl;
    cout << path.size() - 1 << endl;

    for( int i = path.size() - 2; i >=0; i-- ) {
        vector<int> solution (9);
        int dvert = path[i].getNullPosition()%3 - path[i+1].getNullPosition()%3;
        int dhor = path[i].getNullPosition()/3 - path[i+1].getNullPosition()/3;
        if (dvert!= 0){
            if (dvert == -1){cout << "l";}
            if (dvert == 1){cout << "r";}
        }
        if (dhor!= 0){
            if (dhor == -1){cout << "u";}
            if (dhor == 1){cout << "d";}
        }

    }
    cout<<"\n";
}
